{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "start_time": "2023-06-29T15:08:27.091157Z",
     "end_time": "2023-06-29T15:08:27.438856Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "![img](https://image-yangj.oss-cn-beijing.aliyuncs.com/typora/mrp.c1e62649.png)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [],
   "source": [
    "np.random.seed(0)\n",
    "# 定义状态转移概率矩阵\n",
    "P = [\n",
    "    [0.9, 0.1, 0.0, 0.0, 0.0, 0.0],\n",
    "    [0.5, 0.0, 0.5, 0.0, 0.0, 0.0],\n",
    "    [0.0, 0.0, 0.0, 0.6, 0.0, 0.4],\n",
    "    [0.0, 0.0, 0.0, 0.0, 0.3, 0.7],\n",
    "    [0.0, 0.2, 0.3, 0.5, 0.0, 0.0],\n",
    "    [0.0, 0.0, 0.0, 0.0, 0.0, 1.0],\n",
    "]\n",
    "P = np.array(P)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T15:09:20.402015Z",
     "end_time": "2023-06-29T15:09:20.407002Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [],
   "source": [
    "rewards = [-1, -2, -2, 10, 1, 0]  # 定义奖励函数\n",
    "gamma = 0.5  # 定义折扣因子"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T15:10:18.511089Z",
     "end_time": "2023-06-29T15:10:18.539013Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [],
   "source": [
    "def compute_return(start_index, chain, gamma):\n",
    "    \"\"\"\n",
    "    给定一个序列，计算从某个索引（起始状态）开始到最后（终止状态）得到的回报\n",
    "    :param state_index:\n",
    "    :param chain:\n",
    "    :param gamma:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    G = 0\n",
    "    for i in reversed(range(start_index, len(chain))):\n",
    "        # print(i)\n",
    "        G = gamma * G + rewards[chain[i] - 1]\n",
    "    return G"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T15:32:15.622297Z",
     "end_time": "2023-06-29T15:32:15.644240Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "根据本序列计算得到的回报为: -2.5\n"
     ]
    }
   ],
   "source": [
    "# 一个状态序列, s1-s2-s3-s6\n",
    "chain = [1, 2, 3, 6]\n",
    "start_index = 0\n",
    "G = compute_return(start_index, chain, gamma)\n",
    "print(f'根据本序列计算得到的回报为: {G}')"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T15:32:16.105727Z",
     "end_time": "2023-06-29T15:32:16.144626Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "outputs": [],
   "source": [
    "def compute(P, rewards, gamma, states_num):\n",
    "    \"\"\"\n",
    "    利用贝尔曼方程的矩阵形式计算解析解，states_num是MRP的状态数\n",
    "    :param P:\n",
    "    :param rewards:\n",
    "    :param gamma:\n",
    "    :param states_num:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    rewards = np.array(rewards).reshape((-1, 1))  # 将rewards写成列向量形式\n",
    "    value = np.dot(np.linalg.inv(np.eye(states_num, states_num) - gamma * P), rewards)\n",
    "    return value"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T15:39:03.679822Z",
     "end_time": "2023-06-29T15:39:03.719819Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MRP中每个状态价值分别为\n",
      "[[-2.01950168]\n",
      " [-2.21451846]\n",
      " [ 1.16142785]\n",
      " [10.53809283]\n",
      " [ 3.58728554]\n",
      " [ 0.        ]]\n"
     ]
    }
   ],
   "source": [
    "V = compute(P, rewards, gamma, 6)\n",
    "print(f'MRP中每个状态价值分别为\\n{V}')"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T15:39:51.033365Z",
     "end_time": "2023-06-29T15:39:51.056268Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 马尔科夫决策过程(MDP)\n",
    "![img](https://image-yangj.oss-cn-beijing.aliyuncs.com/typora/mdp.aaacb46a.png)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "outputs": [],
   "source": [
    "S = ['s1,', 's2', 's3', 's4', 's5']  #状态集合\n",
    "A = [\"保持s1\", \"前往s1\", \"前往s2\", \"前往s3\", \"前往s4\", \"前往s5\", \"概率前往\"]  # 动作集合\n",
    "#状态转移函数\n",
    "P = {\n",
    "    \"s1-保持s1-s1\": 1.0,\n",
    "    \"s1-前往s2-s2\": 1.0,\n",
    "    \"s2-前往s1-s1\": 1.0,\n",
    "    \"s2-前往s3-s3\": 1.0,\n",
    "    \"s3-前往s4-s4\": 1.0,\n",
    "    \"s3-前往s5-s5\": 1.0,\n",
    "    \"s4-前往s5-s5\": 1.0,\n",
    "    \"s4-概率前往-s2\": 0.2,\n",
    "    \"s4-概率前往-s3\": 0.4,\n",
    "    \"s4-概率前往-s4\": 0.4,\n",
    "}\n",
    "#奖励函数\n",
    "R = {\n",
    "    \"s1-保持s1\": -1,\n",
    "    \"s1-前往s2\": 0,\n",
    "    \"s2-前往s1\": -1,\n",
    "    \"s2-前往s3\": -2,\n",
    "    \"s3-前往s4\": -2,\n",
    "    \"s3-前往s5\": 0,\n",
    "    \"s4-前往s5\": 10,\n",
    "    \"s4-概率前往\": 1,\n",
    "}\n",
    "gamma = 0.5 # 折扣因子\n",
    "MDP = (S,A,P,R,gamma)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T16:04:05.936874Z",
     "end_time": "2023-06-29T16:04:05.970784Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 策略1：随机策略"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "outputs": [],
   "source": [
    "Pi_1 = {\n",
    "    \"s1-保持s1\": 0.5,\n",
    "    \"s1-前往s2\": 0.5,\n",
    "    \"s2-前往s1\": 0.5,\n",
    "    \"s2-前往s3\": 0.5,\n",
    "    \"s3-前往s4\": 0.5,\n",
    "    \"s3-前往s5\": 0.5,\n",
    "    \"s4-前往s5\": 0.5,\n",
    "    \"s4-概率前往\": 0.5,\n",
    "}"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T16:05:09.888168Z",
     "end_time": "2023-06-29T16:05:09.912103Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### 策略2\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "outputs": [],
   "source": [
    "Pi_2 = {\n",
    "    \"s1-保持s1\": 0.6,\n",
    "    \"s1-前往s2\": 0.4,\n",
    "    \"s2-前往s1\": 0.3,\n",
    "    \"s2-前往s3\": 0.7,\n",
    "    \"s3-前往s4\": 0.5,\n",
    "    \"s3-前往s5\": 0.5,\n",
    "    \"s4-前往s5\": 0.1,\n",
    "    \"s4-概率前往\": 0.9,\n",
    "}\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T16:05:25.064261Z",
     "end_time": "2023-06-29T16:05:25.104726Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "outputs": [],
   "source": [
    "# 把输入的两个字符串通过“-”连接，便于使用上述定义的P，R变量\n",
    "def join(str1,str2):\n",
    "    return str1 + \"-\" + str2"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T16:06:20.372882Z",
     "end_time": "2023-06-29T16:06:20.400020Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MDP中每个状态价值分别为\n",
      "[[-1.22555411]\n",
      " [-1.67666232]\n",
      " [ 0.51890482]\n",
      " [ 6.0756193 ]\n",
      " [ 0.        ]]\n"
     ]
    }
   ],
   "source": [
    "gamma = 0.5\n",
    "# 转换后的MRP的状态转移矩阵\n",
    "P_from_mdp_to_mrp = [\n",
    "    [0.5, 0.5, 0.0, 0.0, 0.0],\n",
    "    [0.5, 0.0, 0.5, 0.0, 0.0],\n",
    "    [0.0, 0.0, 0.0, 0.5, 0.5],\n",
    "    [0.0, 0.1, 0.2, 0.2, 0.5],\n",
    "    [0.0, 0.0, 0.0, 0.0, 1.0],\n",
    "]\n",
    "P_from_mdp_to_mrp = np.array(P_from_mdp_to_mrp)\n",
    "R_from_mdp_to_mrp = [-0.5,-1.5,-1.0,5.5,0]\n",
    "\n",
    "V = compute(P_from_mdp_to_mrp,R_from_mdp_to_mrp,gamma,5)\n",
    "print(f'MDP中每个状态价值分别为\\n{V}')"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "start_time": "2023-06-29T16:13:32.121018Z",
     "end_time": "2023-06-29T16:13:32.186841Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
